package com.y.utils;

/**
 * 排序的各种方法
 * @author Y2014188432
 */
public class SortUtil {
    /**
     * 判断待排序数组是否为空（ 只含一个元素的也视为空 ）
     * @param s 待排序数组
     * @return 是否为空 （ true / false ）
     */
    public static boolean isNull(int[] s){
        return s.length == 1 || s.length == 0;
    }

    /**
     * 交换数组的两个元素
     * @param s 数组
     * @param i 数组下标 1
     * @param j 数组下标 2
     */
    public static void swap(int[] s,int i,int j){
        int temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    /**
     * 冒泡排序
     * @param s 待排序数组
     */
    public static void bubbleSort(int[] s){
        if(isNull(s)){
            return;
        }
        for (int i = 0; i < s.length; i++) {
            // flag : 设每轮冒泡未发生交换为 true
            boolean flag = true;
            for (int j = 1; j < s.length - i; j++) {
                if(s[j] < s[j - 1]){
                    swap(s,j,j - 1);
                    // 发生交换则将 flag 置为 false
                    flag = false;
                }
            }
            // 若 该轮未发生交换，则该数组已经为有序数组，结束循环.
            if(flag){
                return;
            }
        }
    }

    /**
     * 选择排序
     * @param s 待排序数组
     */
    public static void chooseSort(int[] s){
        if(isNull(s)){
            return;
        }
        for (int i = 0; i < s.length; i++) {
            for (int j = i; j < s.length; j++) {
                if(s[j] < s[i]){
                    swap(s,i,j);
                }
            }
        }
    }

    /**
     * 插入排序
     * @param s 待排序数组
     */
    public static void insertSort(int[] s){
        if(isNull(s)){
            return;
        }
        for (int i = 1; i < s.length; i++) {
            int mark = i;
            while (mark != 0 && s[mark - 1] > s[mark]){
                swap(s,mark - 1,mark);
                mark --;
            }
        }
    }

    /**
     * 快速排序
     * @param s 待排序数组
     */
    public static void quickSort(int[] s){
        if(isNull(s)){
            return;
        }
        group(s,0,s.length - 1);
    }

    /**
     * 快速算法用:::以区间数组的首部为标准值，分割为两部分
     * @param s 分组
     * @param low 开始下标
     * @param high 结尾下标
     */
    public static void group(int[] s,int low ,int high){
        if(low >= high){
            return;
        }
        int start = low;
        int end = high;
        int temp = s[low];
        while (low < high){
            while (temp <= s[high] && high >low){
                high --;
            }
            s[low] = s[high];
            while (temp >= s[low] && low <high){
                low ++;
            }
            s[high] = s[low];
        }
        s[high] = temp;

        group(s,start,high-1);
        group(s,high+1,end);
    }
}
